Autor: Patryk Rygiel (250080)
GitHub: https://github.com/PatRyg99/ML-PWR-2022
library(ggplot2)
library(grid)
library(gridExtra)
library(ggpubr)
library(ggfortify)
library(cluster)
library(clusterCrit)
library(funtimes)
source("utils/general.R")
source("utils/kmeans.R")
source("utils/pam.R")
irisData <- read.csv("zbiory/iris.data", header=FALSE)
colnames(irisData) <- c("sepal.length", "sepal.width", "petal.length", "petal.width", "class")
head(irisData)
| sepal.length | sepal.width | petal.length | petal.width | class | |
|---|---|---|---|---|---|
| <dbl> | <dbl> | <dbl> | <dbl> | <fct> | |
| 1 | 5.1 | 3.5 | 1.4 | 0.2 | Iris-setosa |
| 2 | 4.9 | 3.0 | 1.4 | 0.2 | Iris-setosa |
| 3 | 4.7 | 3.2 | 1.3 | 0.2 | Iris-setosa |
| 4 | 4.6 | 3.1 | 1.5 | 0.2 | Iris-setosa |
| 5 | 5.0 | 3.6 | 1.4 | 0.2 | Iris-setosa |
| 6 | 5.4 | 3.9 | 1.7 | 0.4 | Iris-setosa |
W ramach tej listy będziemy się zajmować algorytmami grupowania K-means oraz PAM (ang. partitioning around medoids).
Proces działania algorytmu K-means:
Algorytm PAM różni się od K-means tylko krokiem 3. Wartości centroidów są wyznaczane poprzez wyznaczenie centralnego obiektu w klastrze - takiego dla którego odległość dla wszystkich innych elementów klastra jest minimalna. W takiej sytuacji takowy obiekt nazywamy medoidem, zamiast centoidem.
Dla każdej z metod klasteryzacji wykonane zostało 5 prób - w każdej początkowe centroidy są wybierane losowo.
options(repr.plot.width=15, repr.plot.height=12)
G <- clustering.vis.samples(irisData, 4)
Analizując przykładowe klasteryzacje, możemy zauważyć, że algorytm PAM osiąga wizualnie lepsze i bardziej stabilne rezultaty niż K-means. Dla przykładu 3 widzimy, że K-means połączył klastry Iris-versicolor oraz Iris-virginica w jeden klaster i wyznaczył nowy klaster w obrębie klasy Iris-setosa.
Ewidentnie K-means jest wrażliwy na wybór początkowych centroidów, PAM wydaje się być mniej wrażliwy. Prawdopodobnie powodem takiego zachowania jest fakt, że K-means jest bardziej wrażliwy na outliery ze względu na branie średniej, a nie elementu centralnego jako reprezentanta grupującego dla klastra.
Do badania jakości grupowania przez oba algorytmy klasteryzacji będziemy używać dwóch miar, jednej nadzorowanej purity i drugiej nienadzorowanej silhouette.
Purity - (nadzorowana) dla każdego klastra przypisujemy mu klasę na podstawie najczęściej występującej w nim klasy. Następnie sumujemy ile dla każdego klastra dla ile jego elementów ich klasa pokrywa się z klasą przypisaną. Ostatecznie dzielimy sumę przez ilość wszystkich elementów co w rezultacie daje nam wartości z przedziału od 0 do 1 - gdzie im większa wartość tym lepiej.
Silhouette - (nienadzorowana) miara na ile obiekt jest podobny do swojego klastra w porównaniu do innych klastrów. Przyjmuje wartości od -1 do 1 i większa wartość świadczy o lepszym dopasowaniu - odpowiednia konfiguracja klastrów. Miarę można liczyć przy użyciu różnych metryk odległości.
W ramach badanie algorytmu K-means skupimy się na 4 parametrach:
df <- kmeans.maxIters.search(irisData, 10, 20)
G <- kmeans.maxIters.vis(df)
Zauważamy, że dla zbioru Iris algorytm już w pierwszej iteracji osiąga prawie maksymalne wyniki. Widzimy też, że nie potrzebuje od więcej niż 2 iteracji aby zbiec. Brak preprocessingu zdaje się być najlepszym wyborem dla tego zbioru.
df <- kmeans.gridSearch(irisData, 10, 10, c(1, 2, 5, 10))
G <- kmeans.gridSearch.vis(df)
Spodziewanie, dla ilości klastrów równej ilości klas (w tym przypadku 3), wartość miary purity jest najepsza - dla wyższej ilośći klastrów ewidentnie spada. Najlepszym wyborem na parametr nstart jest wartość 10. Jest to także spodziewany wniosek, gdyż im większa ilość początkowo przetestowanych inicjalizacji tym mniejszy wpływ na dobór centroidów ma losowość. Ponownie brak preprocessingu zdaje się być najlepszym wyborem.
Dla miary silhouette natomiast, zauważamy, że spada ona wraz ze wzrostem ilość klastrów, dla dwóch klastrów rezultat jest najepszy. Powodem takiego zachowania prawdopodobnie jest duże podobieństwo pomiędzy klasami Iris-virginica i versicolor co widzieliśmy w procesie wizualizacji.
W ramach badanie algorytmu PAM skupimy się na 3 parametrach:
df <- pam.gridSearch(irisData, 10, 10)
G <- pam.gridSearch.vis(df)
Miary purity oraz silhouette mają podobne trendy jak miało to miejsce dla K-means. Ponownie metody z brakiem standaryzacji zachowuję się lepiej. Metryka manhattan zdaje się być minimalnie lepsza niżeli euclidean.
K-means osiągnęło najlepszy wynik na poziomie ok. 0.89 dla miary purity. PAM natomiast ok. 0.9 dla tej samej miary. Wyniki pomiędzy metodami są dosyć zbliżone, jednak wizualnie algorythm PAM zdaje się być bardziej stabilny i odporny na outliery (co widzimy dla zamieszczonej wizualizacji klastrów).
wineData <- read.csv("zbiory/wine.data", header = FALSE)
colnames(wineData) <- c(
"class", "Alcohol", "Malic.acid", "Ash", "Alcanity.of.ash", "Magnesium",
"Total.phenols", "Flavanoids", "Nonflavanoid.phenosis", "Proanthocyanins",
"Color.intensity", "Hue", "OD280/OD315.of.diluted wine", "Proline"
)
wineData$class=factor(wineData$class)
wineData <- wineData[, c(2:14,1)]
head(wineData)
| Alcohol | Malic.acid | Ash | Alcanity.of.ash | Magnesium | Total.phenols | Flavanoids | Nonflavanoid.phenosis | Proanthocyanins | Color.intensity | Hue | OD280/OD315.of.diluted wine | Proline | class | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| <dbl> | <dbl> | <dbl> | <dbl> | <int> | <dbl> | <dbl> | <dbl> | <dbl> | <dbl> | <dbl> | <dbl> | <int> | <fct> | |
| 1 | 14.23 | 1.71 | 2.43 | 15.6 | 127 | 2.80 | 3.06 | 0.28 | 2.29 | 5.64 | 1.04 | 3.92 | 1065 | 1 |
| 2 | 13.20 | 1.78 | 2.14 | 11.2 | 100 | 2.65 | 2.76 | 0.26 | 1.28 | 4.38 | 1.05 | 3.40 | 1050 | 1 |
| 3 | 13.16 | 2.36 | 2.67 | 18.6 | 101 | 2.80 | 3.24 | 0.30 | 2.81 | 5.68 | 1.03 | 3.17 | 1185 | 1 |
| 4 | 14.37 | 1.95 | 2.50 | 16.8 | 113 | 3.85 | 3.49 | 0.24 | 2.18 | 7.80 | 0.86 | 3.45 | 1480 | 1 |
| 5 | 13.24 | 2.59 | 2.87 | 21.0 | 118 | 2.80 | 2.69 | 0.39 | 1.82 | 4.32 | 1.04 | 2.93 | 735 | 1 |
| 6 | 14.20 | 1.76 | 2.45 | 15.2 | 112 | 3.27 | 3.39 | 0.34 | 1.97 | 6.75 | 1.05 | 2.85 | 1450 | 1 |
Dla każdej z metod klasteryzacji wykonane zostało 5 prób - w każdej początkowe centroidy są wybierane losowo.
options(repr.plot.width=15, repr.plot.height=12)
G <- clustering.vis.samples(wineData, 4)
Klastry dla w zasadzie nie różnią się przy wyborze różnych startowych centroidów. Dla K-means natomiast zauważamy inny rozkład klastrów dla 4 próby. Obie metody nie dokonują poprawnej klasteryzacji na prawdziwe klasy. W pokazanej projekcji, klasy 2 i 3 mocno na siebie nachodzą. Prawdopodobnie jest to powód słabych wyników klastrowania.
df <- kmeans.maxIters.search(wineData, 10, 20)
G <- kmeans.maxIters.vis(df)
Tak jak to miało miejsce dla zbioru Iris, K-means potrzebuje tylko 2-3 iteracje aby całkowicie zbiec. Tym razem zauważamy znacząco przewagę normalizacji i standaryzacji danych dla miary purity. Dla silhouette widzimy odwrotny trend, jednak prawdopodobnie powodem takiego zachowania jest właśnie dominowanie jednej z cech, który dominuje miarę podobieństwa dla tej metryki.
df <- kmeans.gridSearch(wineData, 10, 10, c(1, 2, 5, 10))
G <- kmeans.gridSearch.vis(df)
Tak jak zauważyliśmy wcześniej, zbiór WINE wymaga normalizacji/standaryzacji danych. Wartość nstart jest widocznie lepsza dla wyższych ilości klastrów jednak dla ilości klastrów równej ilości klas 3, różnica jest praktycznie nie zauważalna. Wraz ze wzrostem ilości klastrów zarówno metryka purity jak i silhouette maleją.
df <- pam.gridSearch(wineData, 10, 10)
G <- pam.gridSearch.vis(df)
Dla algorytmu PAM, tak jak dla K-means, widzimy, że normalizacja/standaryzacja danych jest istotna w kontekście dobrej klasteryzacji (metryka purity), natomiast miara silhouette jest nie wymierną metryką, gdy dane nie są zpreprocessowane (powód opisany był w ramach zbioru Iris). Także jak w przypadku K-means, wartości miar spadają wraz ze wzrostem ilości klastrów powyżej ilości klas. Metryka manhattan osiąga minimalnie lepsze rezultaty niż euclidean.
Dla tego zbioru K-means osiąga lepsze rezultaty od PAM w kontekście metryki purity: 0.95 do 0.90. Powodem może być widoczne w wizualizacji nakładanie się klastrów, które najwidoczniej lepiej jest reprezentowalne przy użyciu centroidów niżeli medoidów. Dla tego zbioru także ważna była normalizacja/standaryzacja danych.
glassData <- read.csv("zbiory/glass.data")
colnames(glassData) <- c("index", "RI", "Na", "Mg", "Al", "Si", "K", "Ca", "Ba", "Fe", "class")
glassData <- subset(glassData, select = -c(index))
glassData$class=factor(glassData$class)
head(glassData)
| RI | Na | Mg | Al | Si | K | Ca | Ba | Fe | class | |
|---|---|---|---|---|---|---|---|---|---|---|
| <dbl> | <dbl> | <dbl> | <dbl> | <dbl> | <dbl> | <dbl> | <dbl> | <dbl> | <fct> | |
| 1 | 1.51761 | 13.89 | 3.60 | 1.36 | 72.73 | 0.48 | 7.83 | 0 | 0.00 | 1 |
| 2 | 1.51618 | 13.53 | 3.55 | 1.54 | 72.99 | 0.39 | 7.78 | 0 | 0.00 | 1 |
| 3 | 1.51766 | 13.21 | 3.69 | 1.29 | 72.61 | 0.57 | 8.22 | 0 | 0.00 | 1 |
| 4 | 1.51742 | 13.27 | 3.62 | 1.24 | 73.08 | 0.55 | 8.07 | 0 | 0.00 | 1 |
| 5 | 1.51596 | 12.79 | 3.61 | 1.62 | 72.97 | 0.64 | 8.07 | 0 | 0.26 | 1 |
| 6 | 1.51743 | 13.30 | 3.60 | 1.14 | 73.09 | 0.58 | 8.17 | 0 | 0.00 | 1 |
Dla każdej z metod klasteryzacji wykonane zostało 5 prób - w każdej początkowe centroidy są wybierane losowo.
options(repr.plot.width=15, repr.plot.height=16)
G <- clustering.vis.samples(glassData, 4)
Too few points to calculate an ellipse Too few points to calculate an ellipse Too few points to calculate an ellipse Too few points to calculate an ellipse Too few points to calculate an ellipse Too few points to calculate an ellipse Too few points to calculate an ellipse
Zbiór GLASS ma dwa razy więcej klas niż wcześniej badane zbiory - z tego powodu projekcja na dwie główne składowe zawiera tylko ok. 74% wariancji. Klasy dosyć mocno się na siebie nakładają w kontekście miary co jest powodem dużo gorszych przypasowań klastrów niż widzieliśmy przy poprzednich zbiorach. Ponownie klastry PAM są dosyć podobne przy różnych wyborach początkowych centroidów, natomiast K-means zbiega do różnych ich rozłożeń.
options(repr.plot.width=15, repr.plot.height=12)
df <- kmeans.maxIters.search(glassData, 10, 20)
G <- kmeans.maxIters.vis(df)
Ponownie algorytm zbiega w przeciągu 2-3 iteracji. Co ciekawe brak normalizacji/standaryzacji daje lepsze wyniki zarówno w kontekście purity jak i silhouette.
df <- kmeans.gridSearch(glassData, 10, 10, c(1, 2, 5, 10))
G <- kmeans.gridSearch.vis(df)
Na zbiorze WINE, zauważamy dużą poprawę jaką wprowadza zwiększenie parametru nstart - wrażliwość na wybór początkowych centroidów jest wyższa niż miało to miejsce dla wcześniejszych zbiorów. Co ciekawe miara purity dla 5 klastrów ze standaryzacją osiąga dosyć dobre rezultaty. Jest to ciekawe ze względu na to, że zbiór ma 6 klas. Powodem takiego zachowania może być zły balans klas obecny w zbiorze oraz istotne nakładanie się klas. Miara silhouette natomiast, najlepsze rezultaty osiąga dla mniejszych ilości klastrów, a wraz ze wzrostem ich ilości spada.
df <- pam.gridSearch(glassData, 10, 10)
G <- pam.gridSearch.vis(df)
Tak jak K-means, PAM osiąga lepsze rezultaty bez standaryzacji. Co ciekawe, najlepsze wartości purity są widoczne dla ilości klastrów równej 4 przy ilości klas 6.
K-means ponownie zachowuje się lepiej od PAM: 0.57 do 0.475 dla miary purity i ilości klastrów równej ilości klas. Dla tego zbioru brak zastosowania standaryzacji daje najlepsze rezultaty.
seedsData <- read.csv("zbiory/seeds_dataset.txt", header=FALSE, sep="")
colnames(seedsData) <- c("f1", "f2", "f3", "f4", "f5", "f6", "f7", "class")
seedsData$class=factor(seedsData$class)
head(seedsData)
| f1 | f2 | f3 | f4 | f5 | f6 | f7 | class | |
|---|---|---|---|---|---|---|---|---|
| <dbl> | <dbl> | <dbl> | <dbl> | <dbl> | <dbl> | <dbl> | <fct> | |
| 1 | 15.26 | 14.84 | 0.8710 | 5.763 | 3.312 | 2.221 | 5.220 | 1 |
| 2 | 14.88 | 14.57 | 0.8811 | 5.554 | 3.333 | 1.018 | 4.956 | 1 |
| 3 | 14.29 | 14.09 | 0.9050 | 5.291 | 3.337 | 2.699 | 4.825 | 1 |
| 4 | 13.84 | 13.94 | 0.8955 | 5.324 | 3.379 | 2.259 | 4.805 | 1 |
| 5 | 16.14 | 14.99 | 0.9034 | 5.658 | 3.562 | 1.355 | 5.175 | 1 |
| 6 | 14.38 | 14.21 | 0.8951 | 5.386 | 3.312 | 2.462 | 4.956 | 1 |
Dla każdej z metod klasteryzacji wykonane zostało 5 prób - w każdej początkowe centroidy są wybierane losowo.
options(repr.plot.width=15, repr.plot.height=12)
G <- clustering.vis.samples(seedsData, 4)
Zbiór SEEDS jest najłatwiej separowalnym zbiorem na klastry ze wszystkich rozważanych. Na dwóch głównych składowych bardzo czysto widać podział i oba algorytmy radzą sobie dosyć dobrze z zadaniem.
df <- kmeans.maxIters.search(seedsData, 10, 20)
G <- kmeans.maxIters.vis(df)
Tak jak dla wszystkich badanych zbiorów, ilość iteracji na poziomie 2-3 jest wystarczająca do zbiegnięcia metody. Standaryzacja danych natomiast, osiąga minimalnie lepsze rezultaty od pozostałych form preprocessingu.
df <- kmeans.gridSearch(seedsData, 10, 10, c(1, 2, 5, 10))
G <- kmeans.gridSearch.vis(df)
Trednu purity i silhouette są bardzo zbliżone do tych dla zbiorów WINE oraz IRIS, które także miały 3 klasy. Metoda osiąga najlepsze rezultaty w kontekście purity dla ilości klastrów równej 3. Nie widzimy natomiast dużego wpływu wartości nstart - najwidoczniej wybór początkowych centroidów dla tak łatwego zbioru jak SEEDS jest dosyć łatwy, pojedyczny losowy wybór jest wystarczający.
df <- pam.gridSearch(seedsData, 10, 10)
G <- pam.gridSearch.vis(df)
PAM zachowuje się podobnie jak K-means. Standaryzacja daje minimalnie lepsze wyniki oraz dla 3 klastrów miara purity osiąga największą wartość.
K-means ponownie jest lepszy od PAM: 0.92 do 0.9 w kontekście miary purity. Zbiór SEEDS jest bardzo łatwym zbiorem do klasteryzacji co widzieliśmy przy projekcji na główne składowe.
Odp: Powyżej przedstawione eksperymenty wykazały, że normalizacja i standaryzacja danych mają wpływ na wyniki grupowania. Jednak czasami poprawiają wyniki, a innym razem nie - zależy to od zbioru danych. W teorii, normalizacja czy standaryzacja danych powinny być wskazane dla metod grupowania opartych na mierze odległości (np. PAM), gdyż jedne cechy mogą dominować inne w kontekście tworzenia klastra.
Odp: W K-means klaster jest grupowany przy użyciu centroidu (punkt średni), natomiast w PAM przy użyciu medoidu (punkt centralny w klastrze - o minimalnej odległści do pozostałych elemntów w klastrze).
Odp: K-means jest mniej odporny na szum i wartości odstające, gdyż średnia (centroid) jest bardziej wrażliwa na wartości skrajne niż wybór punktu centralnego (medoid).
Odp: Zastosowanie walidacji krzyżowej w procesie grupowania nie ma zbytniego sensu. Z założenia grupować chcemy zbiory danych, dla których nie znamy poprawnych etykiet elementów i naszym zadaniem jest odkrycie zależności w formie klastrów w obrębie zbioru danych - klasyczne uczenie nienadzorowane. Walidacja krzyżowa ma zastosowanie, gdy korzystamy z metod nadzorowanych w celu ewaluacji jakości modelu. Jednak, gdy takowe posiadamy, nie ma zbytnich powodów żebyśmy korzystali z grupowania nienadzorowanego na rzecz klasyfikatorów nadzorowanych.
Odp: Badane algorytmy klasteryzacji opierają się na losowej inicjalizacji początkowych centroidów. W związku z tym, wyniki pomiędzy odpaleniami algorytmów mogą się różnić, zatem wskazane jest powtórzenie metody parę razy w celu oszacowania wartości metryk jakie osiąga metoda - możemy to robić przez uśrednianie.
Odp: Miara purity mierzy "czystość" klastrów, czyli jak dużo elementów w klastrze należy do klasy dominującej w klastrze. Silhouette natomiast, mierzy jak bardzo elementy są podobne do pozostałych elementów w swoich klastrach.
Odp: Gdy liczba klastrów jest większa niż ilość klas, kilka klastrów będzie posiadać tą samą klasę. W przeciwnym wypadku gdy ilość klastrów jest mniejsza niż ilość klas, istnieją klasy, które nie są przypisane do żadnego z klastrów - chociaż ta sytuacja też może się wydarzyć dla tej samej ilości klastrów jak i większej. Nie są to niepoprawne konfiguracje dla miary purity.